引線的練習實作

規則

為達到節省葉節點指向NULL的空間浪費

說明

• 1.在建立節點的同時，設置左右引線布林值為Ture。
• 2.當節點有向下的子節點，將該位置引線值改為false。
• 3.先利用中序追蹤，建立陣列。
• 4.從根節點開始向下追蹤，遇到布林值為Ture時跳過，表示為引線節點。
• 5.在實線節點時判斷左右分支是否為引線節點，若是則將中序陣列的前後位置存入分支。

函式

void print(tree_p root) {
  printf("\n---------------------------------\n");
  printf("\nInorder:\n");
  new_search(root);
  inorder(root);
}

void inorder(tree_p root) {
  if (root != NULL) {
    if(root->t_left==false){
      inorder(root->left);
    }
    show_line(root);
    if (root->t_right == false) {
      inorder(root->right);
    }
  }
}

void show_line(tree_p point) {
  printf("\n----------%d----------", point->data);
  get_L(point);
  get_R(point);
}

結果

原樹示意圖:

結果顯示:

LR為0表示該分支存在連接節點

LR為1表示該分支為NULL，於是引線連接回去